1941E - Rudolf and k Bridges - CodeForces Solution

from heapq import heappop, heappush
t = int(input())

for _ in range(t):
    n, m, k, d = list(map(int, input().split()))

    grid = [[0 for i in range(m)] for j in range(n)]
    for i in range(n):
        a = list(map(int, input().split()))
        for j in range(m):
            grid[i][j] = a[j]
    
    row = []
    for r in range(n):

                heap = [[0, 0]]
        dp = [0 for i in range(m)]
        for c in range(1, m):
            while heap and c - heap[0][1] - 1 > d:
                heappop(heap)
            dp[c] = heap[0][0] + grid[r][c] + 1
            heappush(heap, [heap[0][0] + grid[r][c] + 1, c])
            
        
        

                heap = [[0, m - 1]]
        dp1 = [0 for i in range(m)]
        for c in range(m - 2, -1, -1):
            while heap and heap[0][1] - c - 1 > d:
                heappop(heap)
            dp1[c] = heap[0][0] + grid[r][c] + 1
            heappush(heap, [heap[0][0] + grid[r][c] + 1, c])
        
        ans = dp[-1] + 2
        for i in range(min(m, d + 2)):
            ans = min(ans, dp1[i] + 2, dp[m - i - 1] + 2)
        
        row.append(ans)

        
            ans = sum(row[:k])
    total = ans
    for i in range(k, n):
        total += row[i] - row[i - k]
        ans = min(ans, total)
    
    print(ans)